<!DOCTYPE html>
    <html>
    <head>
        <meta charset="UTF-8">
        <title>Longest Increasing Subsequence</title>
        <style>
</style>
        
        <link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/markdown.css">
<link rel="stylesheet" href="https://cdn.jsdelivr.net/gh/Microsoft/vscode/extensions/markdown-language-features/media/highlight.css">
<style>
            body {
                font-family: -apple-system, BlinkMacSystemFont, 'Segoe WPC', 'Segoe UI', system-ui, 'Ubuntu', 'Droid Sans', sans-serif;
                font-size: 14px;
                line-height: 1.6;
            }
        </style>
        <style>
.task-list-item { list-style-type: none; } .task-list-item-checkbox { margin-left: -20px; vertical-align: middle; }
</style>
        
        
        
    </head>
    <body class="vscode-light">
        <h1 id="longest-increasing-subsequence">Longest Increasing Subsequence</h1>
<ul>
<li><a href="https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-she-ji-zui-chang-di-zeng-zi-xu-lie">https://labuladong.gitbook.io/algo/dong-tai-gui-hua-xi-lie/dong-tai-gui-hua-she-ji-zui-chang-di-zeng-zi-xu-lie</a></li>
<li><a href="https://www.youtube.com/watch?v=CE2b_-XfVDk&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=7">https://www.youtube.com/watch?v=CE2b_-XfVDk&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=7</a></li>
</ul>
<h1 id="1-基础题目">1. 基础题目</h1>
<ul>
<li>leetcode 300. Longest Increasing Subsequence</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-keyword">import</span> bisect
<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">lengthOfLIS</span><span class="hljs-params">(self, nums: List[int])</span> -&gt; int:</span>
        <span class="hljs-keyword">if</span> <span class="hljs-keyword">not</span> nums:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        n = len(nums)
        tiles = []
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            pos = bisect.bisect_left(tiles, nums[i])
            <span class="hljs-keyword">if</span> pos == len(tiles):
                tiles.append(nums[i])
            <span class="hljs-keyword">else</span>:
                tiles[pos] = nums[i]
        <span class="hljs-keyword">return</span> len(tiles)
</div></code></pre>
<h1 id="2-扩展题目">2. 扩展题目</h1>
<ul>
<li>leetcode 673. Number of Longest Increasing Subsequence</li>
</ul>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span><span class="hljs-params">(object)</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">findNumberOfLIS</span><span class="hljs-params">(self, nums)</span>:</span>
        <span class="hljs-string">"""
        :type nums: List[int]
        :rtype: int
        """</span>
        n = len(nums)
        <span class="hljs-keyword">if</span> n == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        dp = [<span class="hljs-number">1</span>] * (n+<span class="hljs-number">1</span>)
        dp_n = [<span class="hljs-number">1</span>] * (n+<span class="hljs-number">1</span>)
        max_len = <span class="hljs-number">1</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">2</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, i):
                <span class="hljs-keyword">if</span> nums[j<span class="hljs-number">-1</span>] &lt; nums[i<span class="hljs-number">-1</span>]:
                    <span class="hljs-keyword">if</span> dp[j] + <span class="hljs-number">1</span>&gt; dp[i]:
                        dp[i] = dp[j] + <span class="hljs-number">1</span>
                        dp_n[i] = <span class="hljs-number">0</span>
                    <span class="hljs-keyword">if</span> dp[j] + <span class="hljs-number">1</span> == dp[i]:
                        dp_n[i] += dp_n[j]
                    max_len = max(max_len, dp[i])
                   
        <span class="hljs-keyword">return</span> sum([dp_n[i] <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>,n+<span class="hljs-number">1</span>) <span class="hljs-keyword">if</span> dp[i]==max_len ])
</div></code></pre>
<h1 id="3-二维lis-问题">3. 二维LIS 问题</h1>
<ul>
<li>leetcode 354. Russian Doll Envelopes</li>
</ul>
<pre><code><code><div>You have a number of envelopes with widths and heights given as a pair of integers (w, h). One envelope can fit into another if and only if both the width and height of one envelope is greater than the width and height of the other envelope.
What is the maximum number of envelopes can you Russian doll? (put one inside other)
Note:
Rotation is not allowed.
Example:
Input: [[5,4],[6,4],[6,7],[2,3]]
Output: 3 
Explanation: The maximum number of envelopes you can Russian doll is 3 ([2,3] =&gt; [5,4] =&gt; [6,7]).

https://leetcode.com/problems/russian-doll-envelopes/
</div></code></code></pre>
<h2 id="31-第一个dp-算法-时间复杂度-on2--会timeout">3.1 第一个dp 算法， 时间复杂度 O(n^2) , 会timeout</h2>
<p>按照w先排序， 再用dp</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxEnvelopes</span><span class="hljs-params">(self, envelopes: List[List[int]])</span> -&gt; int:</span>
        n = len(envelopes)
        <span class="hljs-keyword">if</span> n == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        envelopes.sort()
        dp = [<span class="hljs-number">1</span>] * (n+<span class="hljs-number">1</span>)
        ans = <span class="hljs-number">1</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">2</span>, n+<span class="hljs-number">1</span>):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, i):
                <span class="hljs-keyword">if</span> envelopes[j<span class="hljs-number">-1</span>][<span class="hljs-number">0</span>] &lt; envelopes[i<span class="hljs-number">-1</span>][<span class="hljs-number">0</span>] <span class="hljs-keyword">and</span> \
                    envelopes[j<span class="hljs-number">-1</span>][<span class="hljs-number">1</span>] &lt; envelopes[i<span class="hljs-number">-1</span>][<span class="hljs-number">1</span>]:
                    dp[i] = max(dp[i], dp[j] + <span class="hljs-number">1</span>)
            ans = max(ans, dp[i])
        <span class="hljs-keyword">return</span> ans
</div></code></pre>
<h2 id="32-第二个二分查找算法参考-300的解法但是有一个技巧">3.2 第二个二分查找算法，参考 300的解法，但是有一个技巧。</h2>
<p>搜索微信 labuladong 的文章 最长递增子序列之信封嵌套问题</p>
<ul>
<li><a href="https://www.sohu.com/a/334550295_478315">https://www.sohu.com/a/334550295_478315</a></li>
</ul>
<ol>
<li>
<p>先对宽度w进行升序排序，如果遇到w相同的情况，则按照高度h降序排序。之后把所有的h作为一个数组，在这个数组上计算 LIS 的长度就是答案。</p>
</li>
<li>
<p>然后在h上寻找最长递增子序列：</p>
<ul>
<li>这个子序列 [2,3],[5,4],[6,7]就是最优的嵌套方案。</li>
<li>这个解法的关键在于，对于宽度w相同的数对，要对其高度h进行降序排序。因为两个宽度相同的信封不能相互包含的，而逆序排序保证在w相同的数对中最多只选取一个计入 LIS。</li>
</ul>
</li>
</ol>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">maxEnvelopes</span><span class="hljs-params">(self, envelopes: List[List[int]])</span> -&gt; int:</span>
        n = len(envelopes)
        <span class="hljs-keyword">if</span> n == <span class="hljs-number">0</span>:
            <span class="hljs-keyword">return</span> <span class="hljs-number">0</span>
        envelopes.sort(key=<span class="hljs-keyword">lambda</span> x:(x[<span class="hljs-number">0</span>], -x[<span class="hljs-number">1</span>]))
        hs = [x[<span class="hljs-number">1</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> envelopes]
        
        tiles = [<span class="hljs-number">0</span>] * n
        tiles_n = <span class="hljs-number">0</span>
        
        <span class="hljs-keyword">for</span> h <span class="hljs-keyword">in</span> hs:
            left = <span class="hljs-number">0</span>
            right = tiles_n
            <span class="hljs-keyword">while</span> left &lt; right:
                mid = (left+right) // <span class="hljs-number">2</span>
                <span class="hljs-keyword">if</span> tiles[mid] &lt; h:
                    left = mid + <span class="hljs-number">1</span>
                <span class="hljs-keyword">else</span>:
                    right = mid
            tiles[left] = h
            tiles_n = max(tiles_n, left+<span class="hljs-number">1</span>)
        <span class="hljs-keyword">return</span> tiles_n
</div></code></pre>
<h1 id="4-box-stacking-dynamic-programming">4. Box Stacking Dynamic Programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=9mod_xRB-O0&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=28">https://www.youtube.com/watch?v=9mod_xRB-O0&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=28</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/BoxStacking.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/BoxStacking.java</a></li>
</ul>
<p>本题就是二维套娃问题，先列出box所有的排列组合，但是要注意， lengh &gt; width, 所以针对 三维是 5,3,2 的box, 只有下面3种放置可能</p>
<pre><code><code><div>length, width, height
5       3      2
5       2      3
3       2      5
</div></code></code></pre>
<p>视频中是按照area 来排序，然后用dp来计算。  我们用#3 题目里面的思路，按照length升序，width降序排列，再用dp，应该也是可以的</p>
<pre><code class="language-java"><div>        <span class="hljs-comment">//apply longest increasing subsequence kind of algorithm on these sorted boxes.</span>
        <span class="hljs-keyword">int</span> T[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[allRotationInput.length];
        <span class="hljs-keyword">int</span> result[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[allRotationInput.length];

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; T.length; i++) {
            T[i] = allRotationInput[i].height;
            result[i] = i;
        }

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">1</span>; i &lt; T.length; i++) {
            <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; i; j++) {
                <span class="hljs-keyword">if</span> (allRotationInput[i].length &lt; allRotationInput[j].length
                        &amp;&amp; allRotationInput[i].width &lt; allRotationInput[j].width) {
                    <span class="hljs-keyword">if</span>( T[j] + allRotationInput[i].height &gt; T[i]){
                        T[i] = T[j] + allRotationInput[i].height;
                        result[i] = j;
                    }
                }
            }
        }
</div></code></pre>
<h1 id="5-maximum-sum-increasing-subsequence-dynamic-programming">5. Maximum Sum Increasing Subsequence Dynamic Programming</h1>
<ul>
<li><a href="https://www.youtube.com/watch?v=99ssGWhLPUE&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=31">https://www.youtube.com/watch?v=99ssGWhLPUE&amp;list=PLrmLmBdmIlpsHaNTPP_jHHDx_os9ItYXr&amp;index=31</a></li>
<li><a href="https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MaximumSumSubsequence.java">https://github.com/mission-peace/interview/blob/master/src/com/interview/dynamic/MaximumSumSubsequence.java</a></li>
</ul>
<p>变形题目， 按照一维的dp求解即可, 求所有递增子序列中 sum 最大的值</p>
<pre><code class="language-java"><div><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">MaximumSumSubsequence</span> </span>{

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">int</span> <span class="hljs-title">maxSum</span><span class="hljs-params">(<span class="hljs-keyword">int</span> arr[])</span></span>{
        <span class="hljs-keyword">int</span> T[] = <span class="hljs-keyword">new</span> <span class="hljs-keyword">int</span>[arr.length];

        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; T.length; i++) {
            T[i] = arr[i];
        }

        <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>; i &lt; T.length; i++){
            <span class="hljs-keyword">for</span>(<span class="hljs-keyword">int</span> j = <span class="hljs-number">0</span>; j &lt; i; j++){
                <span class="hljs-keyword">if</span>(arr[j] &lt; arr[i]){
                    T[i] = Math.max(T[i], T[j] + arr[i]);
                }
            }
        }

        <span class="hljs-keyword">int</span> max = T[<span class="hljs-number">0</span>];
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i=<span class="hljs-number">1</span>; i &lt; T.length; i++){
            <span class="hljs-keyword">if</span>(T[i] &gt; max){
                max = T[i];
            }
        }
        <span class="hljs-keyword">return</span> max;
    }
    
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String args[])</span></span>{
        MaximumSumSubsequence mss = <span class="hljs-keyword">new</span> MaximumSumSubsequence();
        <span class="hljs-keyword">int</span> arr[] = {<span class="hljs-number">1</span>, <span class="hljs-number">101</span>, <span class="hljs-number">10</span>, <span class="hljs-number">2</span>, <span class="hljs-number">3</span>, <span class="hljs-number">100</span>,<span class="hljs-number">4</span>};
        <span class="hljs-keyword">int</span> r = mss.maxSum(arr);
        System.out.print(r);
    }
}
</div></code></pre>
<h1 id="6-lc-1626-best-team-with-no-conflicts">6. LC 1626. Best Team With No Conflicts</h1>
<ul>
<li><a href="https://leetcode.com/problems/best-team-with-no-conflicts/">https://leetcode.com/problems/best-team-with-no-conflicts/</a></li>
</ul>
<p>You are the manager of a basketball team. For the upcoming tournament, you want to choose the team with the highest overall score. The score of the team is the sum of scores of all the players in the team.</p>
<p>However, the basketball team is not allowed to have conflicts. A conflict exists if a younger player has a strictly higher score than an older player. A conflict does not occur between players of the same age.</p>
<p>Given two lists, scores and ages, where each scores[i] and ages[i] represents the score and age of the ith player, respectively, return the highest overall score of all possible basketball teams.</p>
<pre><code><code><div>Example 1:
Input: scores = [1,3,5,10,15], ages = [1,2,3,4,5]
Output: 34
Explanation: You can choose all the players.

Example 2:
Input: scores = [4,5,6,5], ages = [2,1,2,1]
Output: 16
Explanation: It is best to choose the last 3 players. Notice that you are allowed to choose multiple people of the same age.

Example 3:
Input: scores = [1,2,3,5], ages = [8,9,10,1]
Output: 6
Explanation: It is best to choose the first 3 players. 
</div></code></code></pre>
<p>本地和前面信封套娃的区别就是，不严格递增。 两个维度， age和score,  score可以相同， 不严格递增。</p>
<h2 id="我的dp解法一">我的dp解法一</h2>
<p>按照 (age, score) 排序, dp[i]表示以i结尾的组合的最大value</p>
<pre><code class="language-python"><div>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">bestTeamScore</span><span class="hljs-params">(self, scores: List[int], ages: List[int])</span> -&gt; int:</span>

        n = len(scores)
        t = [(ages[i], scores[i]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]
        t.sort()
        ages = [x[<span class="hljs-number">0</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> t]
        scores = [x[<span class="hljs-number">1</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> t]
        
        <span class="hljs-comment">#print(f"{ages}")</span>
        <span class="hljs-comment">#print(f"{scores}")</span>
        
        dp = [<span class="hljs-number">0</span>] * n
        dp[<span class="hljs-number">0</span>] = scores[<span class="hljs-number">0</span>]
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(<span class="hljs-number">1</span>, n):
            dp[i] = scores[i]
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i):
                <span class="hljs-keyword">if</span> (ages[i] == ages[j]) <span class="hljs-keyword">or</span> (ages[i] &gt; ages[j] <span class="hljs-keyword">and</span> scores[i] &gt;= scores[j]):
                    dp[i] = max(dp[i], dp[j] + scores[i])
                    
        <span class="hljs-keyword">return</span> max(dp)
            
            
</div></code></pre>
<h2 id="dp解法二-和-onlgn线段树解法">dp解法二  和 O(nlgn)线段树解法</h2>
<ul>
<li><a href="https://leetcode.com/problems/best-team-with-no-conflicts/discuss/899467/O-(n*log-n)-Dynamic-programming-explanation-source-code-and-video-solution">https://leetcode.com/problems/best-team-with-no-conflicts/discuss/899467/O-(n*log-n)-Dynamic-programming-explanation-source-code-and-video-solution</a></li>
</ul>
<p>Hey everyone, here’s a solution for the 3rd problem.</p>
<p>The idea is explained with an O(n^2) complexity. The O(n * log (n)) solution uses the same idea plus segment trees. The video will be available by the link below.</p>
<p>This is a dynamic programming problem. We sort the players by score, go left to right; store the best possible team score so far; update it from players to the left, considering their ages.</p>
<p>If we consider two players from a team, and the first player has a lower or equal score, then they also have a lower or equal age. So, when we sort a valid team by score, we also sort it by age. Here's a corner case with equal scores, so we actually sort players by score, and then by age.</p>
<p>Now what we are doing is rebuilding our team from a whole sorted set of players.</p>
<p>When we consider a player, we have to check only the next team member for conflicts. Because if that last member doesn’t have conflicts, and is inherently older and more scored than others, then the new, even more old and scored player, won’t have any conflicts for sure. That’s the key.</p>
<ol>
<li>We sort all the players by their score, and by age if scores are equal.</li>
<li>For all the players we store a maximum team score. This is the maximum score of a team where this player is rightmost in our sorting.</li>
<li>Now, for any player, we can form a team without conflicts by adding all the players who have lower ages.</li>
<li>We run a double cycle: on all the players (i), and on all the players with score lower than the current one’s (j):
<ul>
<li>4a. This player (j) can be included into the team of player (i)</li>
<li>4b. The player (i)’s team score equals the maximum score of all players (j) plus the (i)’s player score.</li>
</ul>
</li>
<li>We iterate through all the players and select the maximum team score of all the teams where the current player is the oldest.</li>
</ol>
<p>The point 4 can be done in O(n * log (n)) using segment trees, which will give us a O(n * log(n)) complexity.</p>
<p>先是dp解法,  按照 (score, age) 排序， 和我的dp解法排序不一样</p>
<pre><code class="language-python"><div><span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">bestTeamScore</span><span class="hljs-params">(self, scores: List[int], ages: List[int])</span> -&gt; int:</span>
    
        
        n = len(ages)
        t = [(scores[i], ages[i]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]
        t.sort()
        scores = [x[<span class="hljs-number">0</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> t]
        ages = [x[<span class="hljs-number">1</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> t]
        
        dp = [<span class="hljs-number">0</span>] * (n)
        <span class="hljs-comment">#print(f"{scores} {ages}")</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            <span class="hljs-keyword">for</span> j <span class="hljs-keyword">in</span> range(i):
                <span class="hljs-keyword">if</span> ages[i] &gt;= ages[j] <span class="hljs-keyword">and</span> dp[i] &lt; dp[j]:
                    dp[i] = dp[j]
            dp[i] += scores[i]
        <span class="hljs-keyword">return</span> max(dp)
            
</div></code></pre>
<p>后面是线段树解法，也是按照(score, age)排序</p>
<pre><code class="language-python"><div>

<span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Solution</span>:</span>
    <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">bestTeamScore</span><span class="hljs-params">(self, scores: List[int], ages: List[int])</span> -&gt; int:</span>
        MAXN = <span class="hljs-number">1024</span>
        tree = [<span class="hljs-number">0</span>] * <span class="hljs-number">2</span> * MAXN
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">getMax</span><span class="hljs-params">(l, r)</span>:</span>
            l += MAXN
            r += MAXN
            ans = <span class="hljs-number">0</span>
            <span class="hljs-keyword">while</span> l &lt; r:
                <span class="hljs-keyword">if</span> l &amp; <span class="hljs-number">1</span>:
                    ans = max(ans, tree[l])
                    l += <span class="hljs-number">1</span>
                <span class="hljs-keyword">if</span> r &amp; <span class="hljs-number">1</span>:
                    r -= <span class="hljs-number">1</span>
                    ans = max(ans, tree[r])
                    
                l = l // <span class="hljs-number">2</span>
                r = r // <span class="hljs-number">2</span>
            <span class="hljs-keyword">return</span> ans
        
        <span class="hljs-function"><span class="hljs-keyword">def</span> <span class="hljs-title">setMax</span><span class="hljs-params">(i, v)</span>:</span>
            i += MAXN
            tree[i] = max(tree[i], v)
            <span class="hljs-keyword">while</span> i &gt; <span class="hljs-number">1</span>:
                i = i // <span class="hljs-number">2</span>
                tree[i] = max(tree[i*<span class="hljs-number">2</span>], tree[i*<span class="hljs-number">2</span> + <span class="hljs-number">1</span>])
        
        n = len(ages)
        t = [(scores[i], ages[i]) <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n)]
        t.sort()
        scores = [x[<span class="hljs-number">0</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> t]
        ages = [x[<span class="hljs-number">1</span>] <span class="hljs-keyword">for</span> x <span class="hljs-keyword">in</span> t]
        <span class="hljs-comment">#print(f"{scores} {ages}")</span>
        <span class="hljs-keyword">for</span> i <span class="hljs-keyword">in</span> range(n):
            setMax(ages[i], scores[i] + getMax(<span class="hljs-number">0</span>, ages[i]+<span class="hljs-number">1</span>))
            <span class="hljs-comment">#print(f"i={i} tree={tree}")</span>
        <span class="hljs-keyword">return</span> getMax(<span class="hljs-number">0</span>, MAXN);
            
</div></code></pre>

    </body>
    </html>